Cryptography is a security mechanism for protecting information from unintended disclosure by transforming the information into a form that is unreadable to humans, and unreadable to machines that are not specially adapted to reversing the transformation back to the original information content. The cryptographic transformation can be performed on data that is to be transmitted electronically, such as an electronic mail message, and is equally useful for data that is to be securely stored, such as the account records for customers of a bank or credit company.
In addition to preventing unintended disclosure, cryptography also provides a mechanism for preventing unauthorized alteration of data transmitted or stored in electronic form. After the data has been transformed cryptographically, an unauthorized person is unlikely to be able to determine how to alter the data, because the specific data portion of interest cannot be recognized. Even if the unauthorized user knew the position of the data portion within a data file or message, this position may have been changed by the transformation, preventing the unauthorized person from merely substituting data in place. If an alteration to the transformed data is made by the unauthorized user despite the foregoing difficulties, the fact of the alteration will be readily detectable, so that the data will be considered untrustworthy and not relied upon. This detection occurs when the transformation is reversed; the encrypted date will not reverse to its original contents properly if it has been altered. The same principle prevents unauthorized addition of characters to the data, and deletion of characters from the data, once it has been transformed.
The transformation process performed on the original data is referred to as "encryption." The process of reversing the transformation, to restore the original data, is referred to as "decryption." The terms "encipher" and "decipher" are also used to describe these processes, respectively. A mechanism that can both encipher and decipher is referred to as a "cipher." Data encryption systems are well known in the data processing art. In general, such systems operate by performing an encryption on a plaintext input block, using an encryption key, to produce a ciphertext output block. "Plaintext" refers to the fact that the data is in plain, unencrypted form. "Ciphertext" refers to the fact that the data is in enciphered or encrypted form. The receiver of an encrypted message performs a corresponding decryption operation, using a decryption key, to recover the original plaintext block.
A cipher to be used in a computer system can be implemented in hardware, in software, or in a combination of hardware and software. Hardware chips are available that implement various ciphers. Software algorithms are known in the art as well.
Encryption systems fall into two general categories. Symmetric (or secret key) encryption systems use the same secret key for both encrypting and decrypting messages. An example of a symmetric encryption system is the Data Encryption Standard (DES) system, which is a United States federal standard described in a National Institute of Standards and Technology Federal Information Processing Standard (FIPS Pub 46). In the DES system, a key having 56 independently specified bits is used to convert 64-bit plaintext blocks to 64-bit ciphertext blocks, or vice versa.
Asymmetric (or public key) encryption systems, on the other hand, use two different keys that are not feasibly derivable from one another, one for encryption and another for decryption. A person wishing to receive messages generates a pair of corresponding encryption and decryption keys. The encryption key is made public, while the corresponding decryption key is kept secret. Anyone wishing to communicate with the receiver may encrypt a message using the receiver's public key. Only the receiver may decrypt the message, since only he has the private key. One of the best-known asymmetric encryption systems is the RSA encryption system, named for its originators Rivest, Shamir, and Adleman, and described in U.S. Pat. No. 4,405,829 to Rivest et al., "Cryptographic Communications System and Method."
A public key system is frequently used to encrypt and transmit secret keys for use with a secret key system. A public key system is also used to provide for digital signatures, in which the sender encrypts a signature message using his private key. Because the signature message can only be decrypted with the sender's public key, the recipient can use the sender's public key to confirm that the signature message originated with the sender.
A commonplace method, for both signature generation and signature verification, is to reduce the message M (to be signed) by means of a cryptographic hash function, in which case, the hash of the message, H(M), is signed instead of the message M itself. Signing H(M) requires only one encryption operation whereas M may require several encryption operations, depending on the length of M.
A method for computing digital signatures (e.g., with the RSA algorithm) is described in ANSI Standard X9.31-1998 Digital Signatures Using Reversible Public Key Cryptography For The Financial Services Industry (rDSA). ANSI Standard X9.31 defines procedures for
1. Choosing the public verification exponent, e, PA1 2. Generating the private prime factors, p and q, and public modulus, n=pq, and PA1 3. Calculating the private signature exponent, d. PA1 1. Constraints on p and q relative to e are: PA1 2. The numbers p.+-.1 and q.+-.1 shall have large prime factors greater than 2.sup.100 and less then 2.sup.120, such that: PA1 3. The private prime factor p is the first discovered prime greater than a random number X.sub.p, where ( 2) (2.sup.511+128s).ltoreq.X.sub.p.ltoreq.(2.sup.512+128s -1), and meets the criteria in Nos. 1 and 2 above, and the private prime factor q is the first discovered prime greater than a random number X.sub.q, where ( 2) (2.sup.511+128s).ltoreq.X.sub.q.ltoreq.(2.sup.512+128s -1), and meets the criteria in Nos. 1 and 2 above. s=0, 1, 2, etc. is an integer used to fix the block size. Once selected, the value of s remains constant for the duration of the prime generation procedure. PA1 4. The random numbers X.sub.p and X.sub.q must be different by at least one of their first most significant 100 bits, i.e., .vertline.X.sub.p -X.sub.q.vertline.&gt;2.sup.412+128s. For example, if s=4, so that X.sub.p and X.sub.q are 1024-bit random numbers, then the most significant bit of X.sub.p and the most significant bit of X.sub.q must be "1" and the next most significant 99 bits of X.sub.p and the next most significant 99 bits of X.sub.q must be different in at least 1 bit. Likewise, the private prime factors, p and q, must also satisfy the relationship .vertline.p-q.vertline.&gt;2.sup.412+128s. PA1 If e is odd, then d=e.sup.-1 mod (LCM (p-1, q-1)) PA1 If e is even, then d=e.sup.-1 mod (1/2 LCM (p-1, q-1)) PA1 A. Select a value of s, e.g., s=4. PA1 B. Generate a random number X.sub.p such that ( 2) (2.sup.511+128s).ltoreq.X.sub.p.ltoreq.(2.sup.512+128s -1). PA1 C. Compute the intermediate values: PA1 1. If Y.sub.0 &lt;X.sub.p, replace Y.sub.0 by (Y.sub.0 +p.sub.1 p.sub.2). Y.sub.0 is the least positive integer greater than X.sub.p congruent to (1 mod p.sub.1) and (-1 mod p.sub.2). This ensures that p.sub.1 is a large prime factor of (Y.sub.0 -1) and p.sub.2 is a large prime factor of (Y.sub.0 +1). PA1 2. Search the integer sequence EQU {Y.sub.0, Y.sub.1 =Y.sub.0 +(p.sub.1 p.sub.2), Y.sub.2 =Y.sub.0 +2(p.sub.1 p.sub.2), Y.sub.3 =Y.sub.0 +3(p.sub.1 p.sub.2), . . . , Y.sub.i =Y.sub.0 +i(p.sub.1 p.sub.2)} PA1 in order, where i is an integer.gtoreq.0, until finding a Y.sub.i such that PA1 1. Replace Y.sub.0 with Y.sub.0 +kp.sub.1 p.sub.2, where 0.ltoreq.k.ltoreq.7 is the smallest non-negative integer that makes Y.sub.0 +kp.sub.1 p.sub.2 =3 mod 8. If Y.sub.0 &lt;X.sub.p, replace Y.sub.0 by (Y.sub.0 +8p.sub.1 p.sub.2). Y.sub.0 is the least positive integer greater than X.sub.p congruent to (1 mod p.sub.1) and (-1 mod p.sub.2) and (3 mod 8). PA1 2. Search the integer sequence. EQU {Y.sub.0, Y.sub.1 =Y.sub.0 +(8p.sub.1 p.sub.2), Y.sub.2 =Y.sub.0 +2(8p.sub.1 p.sub.2), Y.sub.3 =Y.sub.0 +3(8p.sub.1 p.sub.2), . . . , Y.sub.i =Y.sub.0 +i(8p.sub.1 p.sub.2)} PA1 in order, where i is an integer.gtoreq.0, until finding a Y.sub.i such that PA1 A. The s used to generate q is the same s used to generate p, e.g., s=4. PA1 B. Generate a random number X.sub.q such that ( 2) (2.sup.511+128s).ltoreq.X.sub.q.ltoreq.(2.sup.512+128s -1). PA1 C. Compute the intermediate values: PA1 1. If Y.sub.0 &lt;X.sub.q, replace Y.sub.0 by (Y.sub.0 +q.sub.1 q.sub.2). Y.sub.0 is the least positive integer greater than X.sub.q congruent to (1 mod q.sub.1) and (-1 mod q.sub.2). This ensures that q.sub.1 is a large prime factor of (Y.sub.0 -1) and q.sub.2 is a large prime factor of (Y.sub.0 +1). PA1 2. Search the integer sequence EQU {Y.sub.0, Y.sub.1 =Y.sub.0 +(q.sub.1 q.sub.2), Y.sub.2 =Y.sub.0 +2(q.sub.1 q.sub.2), Y.sub.3 =Y.sub.0 +3(q.sub.1 q.sub.2), . . . , Y.sub.i =Y.sub.0 +i(q.sub.1 q.sub.2)} PA1 in order, where i is an integer.gtoreq.0, until finding a Y.sub.i such that PA1 1. Replace Y.sub.0 with Y.sub.0 +kq.sub.1 q.sub.2, where 0.ltoreq.k.ltoreq.7 is the smallest non-negative integer that makes Y.sub.0 +kq.sub.1 q.sub.2 =7 mod 8. If Y.sub.0 &lt;X.sub.p, replace Y.sub.0 by (Y.sub.0 +8p.sub.1 p.sub.2). Y.sub.0 is the least positive integer greater than X.sub.q congruent to (1 mod q.sub.1) and (-1 mod q.sub.2) and (7 mod 8). PA1 2. Search the integer sequence. EQU {Y.sub.0, Y.sub.1 =Y.sub.0 +(8q.sub.1 q.sub.2), Y.sub.2 =Y.sub.0 +2(8q.sub.1 q.sub.2), Y.sub.3 =Y.sub.0 +3(8q.sub.1 q.sub.2), . . . , Y.sub.i =Y.sub.0 +i(8q.sub.1 q.sub.2)} PA1 in order, where i is an integer.gtoreq.0, until finding a Y.sub.i such that PA1 1. The inputs to the audit procedure are the public exponent e, the public modulus n, and the six secret SEED values X.sub.p SEED, X.sub.q SEED, X.sub.p1 SEED, X.sub.p2 SEED, X.sub.q1 SEED, and X.sub.q2 SEED. PA1 2. The SEED values X.sub.p SEED, X.sub.q SEED, X.sub.p1 SEED, X.sub.p2 SEED, X.sub.q1 SEED, and X.sub.q2 SEED are hashed, and the random number X.sub.p, X.sub.q, X.sub.p1, X.sub.p2, X.sub.q1 and X.sub.q2, are produced from the generated hash values, respectively, using the same procedure that was used to generate the private prime factors, p and q. PA1 3. The private prime factors, p and q, and the private signature exponent d are re-generated using the same procedure used originally to generate p, q, and d. PA1 4. The generated p and q are multiplied together and the resulting product is compared for equality with the input modulus n. If the two values are equal, then the prime factors were generated according to the rules prescribed in the ANSI X9.31 Standard. Otherwise, the prime factors were not generated according to the rules prescribed in the ANSI X9.31 Standard. PA1 1. Generate X.sub.p1 SEED, and then generate X.sub.p1 from X.sub.p1 SEED. This is a constructive step that cannot fail. PA1 2. Generate p1 from X.sub.p1. This step is an iterative step in which candidate values of p.sub.1 are generated from a single starting value X.sub.p1, in a prescribed order, until a p.sub.1 is found that satisfies a required primality test and a test involving the public verification exponent e. The step can potentially fail in the very unlikely event that the size of the generated p.sub.1 (e.g., 121 bits) is greater than the size of the starting value X.sub.p1 (e.g., 120 bits). If step 2 fails, then repeat steps 1 and 2; otherwise, continue with step 3. PA1 3. Generate X.sub.p2 SEED, and then generate X.sub.p2 from X.sub.p2 SEED. This is a constructive step that cannot fail. PA1 4. Generate p.sub.2 from X.sub.p2. This step is an iterative step in which candidate values of p.sub.2 are generated from a single starting value X.sub.p2, in a prescribed order, until a p.sub.2 is found that satisfies a required primality test and a test involving the public verification exponent e. The step can potentially fail in the very unlikely event that the size of the generated p.sub.2 (e.g., 121 bits) is greater than the size of the starting value X.sub.p2 (e.g., 120 bits). If step 4 fails, then repeat steps 3 and 4; otherwise, continue with step 5. PA1 5. Generate X.sub.p SEED (e.g., consisting of 7 160-bit SEEDs), and then generate X.sub.p from X.sub.p SEED. This step involves a test to ensure that X.sub.p falls within a specified range of allowed values. The step is repeated (possibly several times) until a suitable value of X.sub.p is found. PA1 6. Generate p from X.sub.p. This step is an iterative step in which candidate values of p are generated from a single starting value X.sub.p, in a prescribed order, until a p is found that satisfies a required primality test and a test involving the public verification exponent e. The step can potentially fail in the extremely unlike event that the size of the generated p (e.g., 1025 bits) is greater than the size of the starting value X.sub.p (e.g., 1024 bits). If step 6 fails, then repeat steps 5 and 6; otherwise, continue with step 7 PA1 7. Generate X.sub.q1 SEED, and then generate X.sub.q1 from X.sub.q1 SEED. This is a constructive step that cannot fail. PA1 8. Generate q.sub.1 from X.sub.q1. This step is an iterative step in which candidate values of q.sub.1 are generated from a single starting value X.sub.q1, in a prescribed order, until a q.sub.1 is found that satisfies a required primality test and a test involving the public verification exponent e. The step can potentially fail in the very unlikely event that the size of the generated q.sub.1 (e.g., 121 bits) is greater than the size of the starting value X.sub.q1 (e.g., 120 bits). If step 8 fails, then repeat steps 7 and 8; otherwise, continue with step 9. PA1 9. Generate X.sub.q2 SEED, and then generate X.sub.q2 from X.sub.q2 SEED. This is a constructive step that cannot fail. PA1 10. Generate q.sub.2 from X.sub.q2. This step is an iterative step in which candidate values of q.sub.2 are generated from a single starting value X.sub.q2, in a prescribed order, until a q.sub.2 is found that satisfies a required primality test and a test involving the public verification exponent e. The step can potentially fail in the very unlikely event that the size of the generated q.sub.2 (e.g., 121 bits) is greater than the size of the starting value X.sub.q2 (e.g., 120 bits). If step 10 fails, then repeat steps 9 and 10; otherwise, continue with step 11. PA1 11. Generate X.sub.q SEED (e.g., consisting of 7 160-bit SEEDs), and then generate X.sub.q from X.sub.q SEED. This step involves a test to ensure that X.sub.q falls within a specified range of allowed values and that .vertline.X.sub.p -X.sub.q.vertline. is greater than a specified value. The step is repeated (possibly several times) until a suitable value of X.sub.q is found. PA1 12. Generate q from X.sub.q. This step is an iterative step in which candidate values of q are generated from a single starting value X.sub.q, in a prescribed order, until a q is found that satisfies a required primality test and a test involving the public verification exponent e and a test to ensure that .vertline.p-q.vertline. is greater than a value. The step can potentially fail in the extremely unlikely event that the size of the generated q (e.g., 1025 bits) is greater than the size of the starting value X.sub.q (e.g., 1024 bits). If step 12 fails, then repeat steps 11 and 12; otherwise, continue with step 13. PA1 13. Generate the private signature exponent d from e, p and q. Then test d to ensure that it is smaller than a specified value. In the extremely rare event that the test on d fails, repeat steps 7 through 13; otherwise stop. PA1 1. For a modulus with 1024-bit primes, approximately 2880 bits of extra SEED values (X.sub.p SEED, X.sub.q SEED, X.sub.p1 SEED, X.sub.p2 SEED, X.sub.q1 SEED, and X.sub.q2 SEED) would need to be carried with each private key. This more than triples the number of secret bits that need to be carried in the "private key." PA1 2. Although the ANSI X9.31 Standard recommends that the SEED values be retained with the private key, some implementers may object to this (e.g., when the key is stored on a smart card or when the key is input to a cryptographic function or cryptographic hardware to perform a cryptographic operation), and they may elect to retain the SEED values separately from the private key. But keeping the SEED values separate from the private key has even worse ramifications. In that case, the SEED values may become lost or damaged, in which case the audit function is crippled or rendered ineffective, and most likely the signature key is also rendered ineffective. The user must also protect the secrecy of the of the SEED values, since if the SEED values are discovered by an adversary, they can be easily used to generate the primes and private key, and hence to forge signatures. Storing the private key and SEED values in two different locations means that there are now two targets or points of attack for the adversary, not just one. Thus, when the audit feature is used, the honest user must take extra special steps to the SEEDs from becoming lost or damaged and to protect the secrecy of the SEEDs. This places an extra burden on the user. PA1 3. The SEED values are independent, and there is no apparent need for this. Consequently, it might be possible for an insider attacker to exploit this degree of independence to attack the procedure.
The procedure for signing a message M (signature production) consists of the following steps: M is hashed using a cryptographic hash function H to produce a hash value H(M). H(M) is then encapsulated within a data structure IR, a representative element RR is computed from IR, and RR is raised to the power d modulo n. The signature .SIGMA. is either the result or its complement to n, whichever is smaller. That is, .SIGMA.=min{RR.sup.d mod n, n-(RR.sup.d mod n)}. The signature .SIGMA. is exactly one bit less in length than the length of the modulus n. The message and signature (M, .SIGMA.) are then sent to the receiver for verification.
The procedure for verifying a signature (signature verification) consists of the following steps: The verifier treats the message and signature as (M', .SIGMA.') until the signature verification is successful, and it is proven that M=M' and .SIGMA.=.SIGMA.'. The signature .SIGMA.' is raised to the power e mod n in order to obtain the intermediate integer RR'. That is, RR'=(.SIGMA.').sup.e mod n. The intermediate integer IR' is then computed from RR' as a function of the least significant (right most) bits of RR'. A sanity check is then performed on IR', and if this step succeeds, the value of H(M)' is then recovered from IR'. Finally, a hash is computed on the message M', and the computed value of H(M') is compared for equality with the recovered value of H(M)'. The verification process succeeds if the two values are equal and it fails if the two values are not equal.
The public exponent is a positive integer e, where 2.ltoreq.e.ltoreq.2.sup.k-160, and k is the length of the modulus n in bits. The public exponent may be selected as a fixed value or generated as a random value. When e is odd, the digital signature algorithm is called RSA. When e is even, the digital signature algorithm is called Rabin-Williams. Common fixed values for e are 2, 3, 17, and 2.sup.16 +1=65,537.
The public modulus, n, is the product of two distinct positive primes, p and q (i.e., n=pq).
The private prime factors, p and q, are secretly and randomly selected by each signing entity. The private prime factors must satisfy several conditions, as follows:
If e is odd, then e shall be relatively prime to both p-1 and q-1. PA2 If e is even, then p shall be congruent to 3 mod 8, q shall be congruent to 7 mod 8, and e shall be relatively prime to both (p-1)/2 and (q-1)/2. PA2 p-1 has a prime factor denoted by p.sub.1 PA2 p+1 has a prime factor denoted by p.sub.2 PA2 q-1 has a prime factor denoted by q.sub.1 PA2 q+1 has a prime factor denoted by q.sub.2 PA2 where LCM denotes "Least Common Multiple." In the rare event that d.ltoreq.2.sup.512+128s, then the key generation process is repeated with new seeds for X.sub.q1, X.sub.q2, and X.sub.q. The random numbers X.sub.q1 and X.sub.q2 are defined below. PA2 R.sub.p =(p.sub.2.sup.-1 mod p.sub.1)p.sub.2 -(p.sub.1.sup.-1 mod p.sub.2)p.sub.1. If R.sub.p &lt;0, then replace R.sub.p by R.sub.p +p.sub.1 p.sub.2. PA2 Y.sub.0 =X.sub.p +(R.sub.p -X.sub.p mod p.sub.1 p.sub.2). PA2 Y.sub.i is prime and PA2 GCD (Y.sub.i -1, e)=1 PA2 Y.sub.i is prime and PA2 GCD ((Y.sub.i -1)/2, e)=1, and Y.sub.i =3 mod 8 PA2 in which case, p=Y.sub.i. PA2 R.sub.q =(q.sub.2.sup.-1 mod q.sub.1)q.sub.2 -(q.sub.1.sup.-1 mod q.sub.2)q.sub.1. If R.sub.q &lt;0, then replace R.sub.q by R.sub.q +q.sub.1 q.sub.2. PA2 Y.sub.0 =X.sub.q +(R.sub.q -X.sub.q mod q.sub.1 q.sub.2). PA2 Y.sub.i is prime and PA2 GCD (Y.sub.i -1, e)=1 PA2 in which case, q=Y.sub.i. PA2 Y.sub.i is prime and PA2 GCD ((Y.sub.i -1)/2, e)=1, and Y.sub.i =7 mod 8 PA2 in which case, q=Y.sub.i.
The private signature exponent, d, is a positive integer such that d&gt;2.sup.512+128s. That is, the length of d must be at least half the length of the modulus n. d is calculated as follows:
The candidates for the private prime factors, p and q, are constructed using the large prime factors, p.sub.1, p.sub.2, q.sub.1, and q.sub.2, and the Chinese Remainder Theorem (see A. Menezes, P. C. Van Oorschot, and S. Vanstone, Handbook of Applied Cryptography, CRC Press, 1997.)
The large prime factors p.sub.1, p.sub.2, q.sub.1, and q.sub.2, are generated from four generated random numbers X.sub.p1, X.sub.p2, X.sub.q1 and X.sub.q2. The random numbers are chosen from an interval [2.sup.100+a, 2.sup.101+a -1] where "a" satisfies 0.ltoreq.a.ltoreq.20. For example, if a=19, then the random numbers are randomly selected from the interval [2.sup.119, 2.sup.120 -1], in which case the random numbers each have 120 bits, where the most significant bit of each generated number X.sub.p1, X.sub.p2, X.sub.q1 and X.sub.q2 is "1." If a pseudo random number generator (PRNG) is used, it is recommended that the four random numbers should be generated from 4 separate input seeds.
The p.sub.1, p.sub.2, q.sub.1, and q.sub.2, are the first primes greater than their respective random X values (X.sub.p1, X.sub.p2, X.sub.q1 and X.sub.q2) and such that they are mutually prime with the public exponent e. That is, e must not contain a factor equal to p.sub.1, p.sub.2, q.sub.1, or q.sub.2.
The procedure to generate the private prime factor p is as follows:
If e is odd, do the following:
where GCD is Greatest Common Divisor, in which case, p=Y.sub.i.
If e is even, do the following:
The procedure to generate the private prime factor q is as follows:
If e is odd, do the following:
If e is even, do the following:
As mentioned above, the value .vertline.X.sub.p -X.sub.q.vertline. must be &gt;2.sup.412+128s. If not, then another X.sub.q is generated, and a new value of q is computed. This step is repeated until the constraint is satisfied. Likewise, the generated values of p and q must satisfy the relation .vertline.p-q.vertline.&gt;2.sup.412+128s.
Note that it is very unlikely that the test on .vertline.X.sub.p -X.sub.q.vertline. would succeed and the test on .vertline.p-q.vertline. would fail. Note also that according to the X9.31 Standard, if a pseudo random number generator is used to generate random numbers, then separate seeds should be used to generate X.sub.p and X.sub.q.
Altogether there are six random numbers X.sub.i needed in the generation of the private prime factors, p and q, namely X.sub.p, X.sub.p1, X.sub.p2, X.sub.q, X.sub.q1 and X.sub.q2. These random numbers are generated by either a true noise hardware randomizer (RNG) or via a pseudo random generator (PRNG).
The random numbers X.sub.i are generated differently depending on whether or not the process of generating the private prime factors (p and q) requires the capability to be audited later by an independent third party.
In the case where no audit is required, the outputs of the RNG and the PRNG are used directly as the random numbers X.sub.i. In the case where audit is required, the outputs of the RNG and the PRNG are used as intermediate values, called SEED (upper case) values, and these SEED values are then hashed to produce the random numbers X.sub.i. That is, when an audit capability is required, an extra hashing step is used in the generation of the random numbers X.sub.i.
The PRNG itself makes use of an input seed (lower case), which is different from the generated SEED values. Thus, when an audit capability is required and a PRNG is used, a random seed (lower case) is input to the PRNG and a SEED (upper case) is output from the PRNG. The SEEDs should have at least 160 bits of entropy.
To illustrate the process, suppose that one wishes to generate a 1024 bit random number X.sub.i using SHA-1 as the hash algorithm--see ANSI Standard X9.30-1996, Public Key Cryptography Using Irreversible Algorithms for the Financial Services Industry, Part 2: The Secure Hash Algorithm-1 (SHA-1). Since the output hash value from SHA-1 is 160 bits, the optimal method for generating an X.sub.i of 1024 bits is to generate 7 160-bit SEED values, denoted SEED1 through SEED7, hash each of these SEED values with SHA-1 to produce 7 corresponding 160-bit hash values, denoted hash1 through hash7, and then extract 1024 bits from the available 1120 bits, e.g., by concatenating the values hash1 through hash6 together with 64 bits taken from hash7. The method for generating a 120-bit X.sub.i is more straightforward. In this case, a single 160-bit SEED is generated and then hashed, and 120 bits are taken from the resulting hash value. The concatenation of the 7 SEED values used in generating each of X.sub.p and X.sub.q are denoted X.sub.p SEED and X.sub.q SEED, respectively. The single SEED values used in generating X.sub.p1, X.sub.p2, X.sub.q1 and X.sub.q2 are denoted X.sub.p1 SEED, X.sub.p2 SEED, X.sub.q1 SEED, and X.sub.q2 SEED, respectively.
In order to allow for audit, the SEED values X.sub.p SEED, X.sub.q SEED, X.sub.p1 SEED, X.sub.p2 SEED, X.sub.q1 SEED, and X.sub.q2 SEED must be saved, and they must be available in case an audit is required.. The SEED values must also be kept secret. It is recommended that the SEED values (X.sub.p SEED, X.sub.q SEED, X.sub.p1 SEED, X.sub.p2 SEED, X.sub.q1 SEED, and X.sub.q2 SEED) be retained with the private key as evidence that the primes were generated in an arbitrary manner.
The procedure for auditing the generation procedure (i.e., the generation of the private prime factors, p and q) is a follows:
The audit procedure is specifically designed to defend against a so-called First Party Attack. In a first party attack, a user purposely generates a large number of candidate prime numbers until one is found that has some mathematical weakness. Later, the user repudiates one or more of his generated signatures by showing that a weakness exists in one of his primes and claiming that the weakness was discovered and exploited by an adversary. In such a case, the user (or First Party) does not follow the prescribed ANSI X9.31 private prime factor generation procedure, but instead uses a different method to purposely construct primes that have a desired weakness
But, the ANSI X9.31 method of prime number generation--hashing SEED values to generate the needed random numbers, X.sub.i --prevents an insider from starting with an intentionally constructed "bad prime" and working backwards to derive the SEED(s) needed to generate the prime. Whereas, it might be possible to start with a constructed "bad prime" and invert the steps to obtain the corresponding random number X.sub.i (needed to produce the "bad prime"), it is not possible to invert the hash function to determine the required input SEED(s) that will produce X.sub.i. In effect, the method of using hash values forces the user to generate his primes using a "forward process." This means that the only way a "bad prime" can be produced is by pure chance--by repeatedly selecting different starting SEED values and generating primes from these SEED values until a "bad prime" happens to be produced. However, the probability of such a chance event is very small, in fact small enough so that (for practical purposes) a user will never be able to find a "bad prime" using trial and error.
The procedure for generating the private prime factors (p and q) and the private signature exponent d can be specified in terms of the following abbreviated steps:
The ANSI X9.31 prescribed audit procedure has certain disadvantages.
Accordingly, a need exists for an improved and more flexible audit procedure that retains the advantages of the present ANSI X9.31 audit procedure, but eliminates its disadvantages. More particularly, a need exists for an audit procedure that does not require secret SEED values to be retained with the private key and made available whenever the audit procedure is required to be performed. In addition, a need exists for a private prime factor generation procedure that incorporates fewer degrees of freedom in the selection of random numbers required by the procedure, while at the same time providing sufficient entropy in the generated random numbers, thereby providing a strong generation procedure while at the same time affording an adversary less freedom to exploit and potentially attack the generation procedure.
The present invention achieves these objectives by encoding the initial secret seed values into the generated primes themselves. An optional nonsecret initialization value (IV) can also be specified to the generation procedure. This provides an additional source of entropy for the generation of the primes. For example, if two 1024-bit primes (p and q) are generated, then the method of the invention permits seed values with a combined entropy of 2048 bits to be used to generate these primes.
One of the inherent limitations of the generation procedure is that it is not possible to construct n-bit primes with n bits of entropy, where the seeds used to generated these primes are encoded wholly into the generated primes. Thus, a must choose whether to (1) generate n-bit primes using less than n bits of entropy, in order that the seeds can be encoded into the generated primes, or (2) generate n-bit primes using a full n bits of entropy, thus implying the need for a initialization value (IV) that must be retained or regenerated in case of audit. It is, therefore, desirable to find a convenient method for implementing an IV.
The generation procedure can be audited using only the generated cryptographic variables (n=pq, d, and e) and the optional IV, where n is the public modulus, d is the generated private signature exponent, e is the public verification exponent and IV is the (optional) initialization value. It is unnecessary for the user to retain the primes (p and q), since an efficient procedure exists to compute these primes from n, d, and e.